package special.graph;

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        // 一个带权重的图的邻接矩阵表示
        int[][] graph = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };

        int[] shortestDistances = dijkstra(graph, 0);

        for (int i = 0; i < shortestDistances.length; i++) {
            System.out.println("Shortest distance from node 0 to node " + i + " is " + shortestDistances[i]);
        }
    }

    public static int[] dijkstra(int[][] graph, int source) {
        int numNodes = graph.length;
        int[] shortestDistances = new int[numNodes];
        boolean[] visited = new boolean[numNodes];

        // 初始化最短路径数组和访问状态数组
        for (int i = 0; i < numNodes; i++) {
            shortestDistances[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        // 设置起始节点的最短路径为0
        shortestDistances[source] = 0;

        // 找到从起始节点到所有其他节点的最短路径
        for (int i = 0; i < numNodes - 1; i++) {
            int minDistance = Integer.MAX_VALUE;
            int minIndex = -1;

            // 选择当前未访问的节点中最短路径的节点
            for (int j = 0; j < numNodes; j++) {
                if (!visited[j] && shortestDistances[j] < minDistance) {
                    minDistance = shortestDistances[j];
                    minIndex = j;
                }
            }

            // 标记选中的节点为已访问
            visited[minIndex] = true;

            // 更新最短路径数组
            for (int j = 0; j < numNodes; j++) {
                if (!visited[j] && graph[minIndex][j] != 0 && shortestDistances[minIndex] != Integer.MAX_VALUE
                        && shortestDistances[minIndex] + graph[minIndex][j] < shortestDistances[j]) {
                    shortestDistances[j] = shortestDistances[minIndex] + graph[minIndex][j];
                }
            }
        }

        return shortestDistances;
    }
}
